// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-31 17:30
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetcodeRepeat;

import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * 最繁忙服务器记录
 */
@SuppressWarnings("ALL")
public class BusiestServers {
    /**
     * 使用线段树
     *
     * @param k
     * @param arrival
     * @param load
     * @return
     */
    public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
        int n = arrival.length, max = 0;
        int[] cnt = new int[k];
        root = buildSegTree(0, k - 1);
        for (int i = 0; i < n; i++) {
            int task = arrival[i];
            if (task < root.endTime) {
                continue;
            }
            int search = search(root, i % k, k, arrival[i]);
            if (search == -1) {
                search = search(root, 0, i % k - 1, arrival[i]);
            }
            update(root, search, arrival[i] + load[i]);
            max = Math.max(max, ++cnt[search]);
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            if (cnt[i] == max) {
                ans.add(i);
            }
        }
        return ans;
    }

    /*
        1 定义线段树节点
        2 定义线段树创建方法
        3 线段树的初始化操作
        4 线段树查找和更新方法

     */

    Node root;

    class Node {
        // 线段树的叶子节点表征的是服务器，通过服务器的endTime可以判断当前服务器是否空闲
        int endTime;
        // 线段树是一个索引二叉树，使用指针的方式指向，当前节点的左右子树
        Node left, right;
        // start和end节点记录了当前节点的信息区间，如果当前节点表征的是服务器节点，则有left == right
        int start, end;

        public Node(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    /**
     * @param left
     * @param right
     */
    public Node buildSegTree(int left, int right) {
        Node root = new Node(left, right);
        if (left == right) {
            // 需要创建的线段是只是一个节点
            return root;
        }
        int middle = left + ((right - left) >> 1);
        root.left = buildSegTree(left, middle);
        root.right = buildSegTree(middle + 1, right);
        return root;
    }

    /**
     * 返回特定空闲服务器
     *
     * @param left:起始服务器区间
     * @param right:结束服务器区间
     * @param arrival:任务到达时间
     * @return
     */
    public int search(Node root, int left, int right, int arrival) {
        if (root.start == root.end) {
            if (root.start >= left && root.end <= right) {
                return root.start;
            }
            return -1;
        }
        int val = -1, middle = root.start + ((root.end - root.start) >> 1);
        if (left <= middle && root.left.endTime <= arrival) {
            val = search(root.left, left, right, arrival);
        }
        if (val != -1) {
            return val;
        }
        if (right > middle && root.right.endTime <= arrival) {
            val = search(root.right, left, right, arrival);
        }
        return val;
    }


    /**
     * 树状数组的更新方法
     */
    public void update(Node root, int index, int endTime) {
        if (root.start == root.end) {
            if (root.start == index) {
                root.endTime = endTime;
            }
            return;
        }
        int mid = root.start + ((root.end - root.start) >> 1);
        if (index > mid) {
            update(root.right, index, endTime);
        } else {
            update(root.left, index, endTime);
        }
        root.endTime = Math.min(root.left.endTime, root.right.endTime);
    }


    @Test
    public void shout() {
        int k = 13;
        int[] arrival = {5, 6, 7, 9, 12, 14, 15, 16, 20, 21, 22, 24, 27, 28, 31, 32, 34, 36};
        int[] load = {6, 9, 22, 20, 27, 12, 20, 9, 5, 33, 3, 20, 16, 26, 36, 22, 26, 13};
        System.out.println(busiestServers(k, arrival, load));
    }

//    /**
//     * 优先队列 + 红黑树
//     *
//     * @param k
//     * @param arrival
//     * @param load
//     * @return
//     */
//    public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
//        /*-----辅助数据结构创建-----*/
//        PriorityQueue<Tuple> busyService = new PriorityQueue<>((a, b) -> {
//            if (a.endTime != b.endTime) {
//                return a.endTime - b.endTime;
//            } else {
//                return a.Index - b.Index;
//            }
//        });
//        TreeSet<Integer> freeService = new TreeSet<>();
//        /*-----数据初始化-----*/
//        int n = arrival.length, max = 0, N = 100010;
//        /*-----动态处理数据-----*/
//        int[] cnt = new int[N];
//        Arrays.fill(cnt, 0);
//        for (int i = 0; i < k; i++) {
//            freeService.add(i);
//        }
//        for (int i = 0; i < n; i++) {
//            // 先从繁忙服务器堆中取出空闲服务器
//            int start = arrival[i], end = start + load[i];
//            while (!busyService.isEmpty() && busyService.peek().endTime <= start) {
//                freeService.add(busyService.poll().Index);
//            }
//            Integer u = freeService.ceiling(i % k);
//            if (u == null) {
//                u = freeService.ceiling(0);
//            }
//            if (u == null) {
//                continue;
//            }
//            freeService.remove(u);
//            busyService.add(new Tuple(u, end));
//            max = Math.max(max, ++cnt[u]);
//        }
//        /*-----获取答案列表-----*/
//        List<Integer> ans = new ArrayList<>();
//        for (int i = 0; i < k; i++) {
//            if (cnt[i] == max) {
//                ans.add(i);
//            }
//        }
//        return ans;
//    }


//    class Tuple implements Comparable<Tuple> {
//        private int Index, endTime;
//
//        public Tuple(int index, int endTime) {
//            Index = index;
//            this.endTime = endTime;
//        }
//
//        @Override
//        public int compareTo(Tuple b) {
//            if (this.Index == b.Index) {
//                if (this.endTime >= b.endTime) {
//                    return 0;
//                }
//            }
//            if (this.endTime != b.endTime) {
//                return this.endTime - b.endTime;
//            }
//            return -this.Index + b.Index;
//
//        }
//
//        @Override
//        public boolean equals(Object o) {
//            if (this == o) {
//                return true;
//            }
//            if (o == null || getClass() != o.getClass()) {
//                return false;
//            }
//            Tuple tuple = (Tuple) o;
//            return Index == tuple.Index && endTime == tuple.endTime;
//        }
//
//        @Override
//        public int hashCode() {
//            return Objects.hash(Index, endTime);
//        }
//    }
//
//
//    public List<Integer> busiestServersT(int k, int[] arrival, int[] load) {
//        int N = 100010;
//        int[] cnt = new int[N];
//        int n = arrival.length, max = 0;
//        PriorityQueue<int[]> busyService = new PriorityQueue<>((a, b) -> a[1] - b[1]);
//        Arrays.fill(cnt, 0);
//        TreeSet<Integer> freeService = new TreeSet<>();
//        for (int i = 0; i < n; i++) {
//            freeService.add(i);
//        }
//        for (int i = 0; i < n; i++) {
//            int start = arrival[i], end = start + load[i];
//            while (!busyService.isEmpty() && busyService.peek()[1] <= start) {
//                freeService.add(busyService.poll()[0]);
//            }
//            Integer ceiling = freeService.ceiling(i % k);
//            if (ceiling == null) {
//                ceiling = freeService.ceiling(0);
//            }
//            if (ceiling == null) {
//                continue;
//            }
//            freeService.remove(ceiling);
//            busyService.offer(new int[]{ceiling, end});
//            max = Math.max(max, ++cnt[ceiling]);
//        }
//        ArrayList<Integer> ans = new ArrayList<>();
//        for (int i = 0; i < k; i++) {
//            if (cnt[i] == max) {
//                ans.add(i);
//            }
//        }
//        return ans;
//    }
//
//    public List<Integer> busiestServersTT(int k, int[] arrival, int[] load) {
//        int n = arrival.length, max = 0;
//        /*-----初始化服务器-----*/
//        int[] service = new int[k], workNum = new int[k];
//        tag:
//        for (int i = 0; i < n; i++) {
//            // 当前任务指定服务器
//            int cur = i % k, isLoop = cur;
//            while ((service[cur] - arrival[i]) > 0) {
//                // 服务器构成一个环，当指定服务器仍然繁忙的时候，需要查找下一个空闲服务器
//                cur = (cur + 1) % k;
//                if (cur == isLoop) {
//                    // 当所有服务器都在工作的时候，丢弃当前的任务
//                    continue tag;
//                }
//            }
//            workNum[cur]++;
//            max = Math.max(max, workNum[cur]);
//            /*
//                工作时间是从arrival时间开始的
//             */
//            service[cur] = arrival[i] + load[i];
//        }
//        List<Integer> res = new ArrayList<Integer>();
//        for (int i = 0; i < k; i++) {
//            if (workNum[i] == max) {
//                res.add(i);
//            }
//        }
//        return res;
//    }
//
//


}
